import math
from .linked_binary_tree import LinkedBinaryTree
from .map_base import MapBase


class BinarySearchTree(LinkedBinaryTree, MapBase):
    """Sorted map implementation using a bianry search tree"""

    class Position(LinkedBinaryTree.Position):
        def key(self):
            """Return key of map's key-value pair"""
            return self.element()._key

        def value(self):
            """Return value of map's key-value pair"""
            return self.element()._value

    def _subtree_search(self, p, k):
        """返回搜索p的子树中键值为k的位置，否则返回搜索到最后一个节点的位置"""
        if k == p.key():
            return p
        elif k < p.key():
            if self.left(p) is not None:
                return self._subtree_search(self.left(p), k)
        else:
            if self.right(p) is not None:
                return self._subtree_search(self.right(p), k)
        return p

    def _subtree_first_position(self, p):
        """搜索子根为p的子树中第一个位置，即左子树中最小位置"""
        walk = p
        while self.left(walk) is not None:
            walk = self.left(walk)
        return walk

    def _subtree_last_position(self, p):
        """搜索子根为p的子树中最后一个位置，即右子树中最大位置"""
        walk = p
        while self.right(walk) is not None:
            walk = self.right(walk)
        return walk

    def first(self):
        """Return the first Position in the tree"""
        return self._subtree_first_position(self.root()) if len(self) > 0 else None

    def last(self):
        """Return the last Position in the tree"""
        return self._subtree_last_position(self.right()) if len(self) > 0 else None

    def before(self, p):
        """Return the Position just before p in the natural order.
        Return None if p is the first position.
        """
        self._validate(p)

        if self.left(p):
            return self._subtree_last_position(self.left(p))
        else:
            walk = p # walk upward
            above = self.parent(walk)
            while above is not None and walk == self.left(above):
                walk = above
                above = self.parent(walk)
            return above

    def after(self, p):
        """Return the Position just after p in the natural order.
        Return None if p is the last position.
        """
        self._validate(p)
        if self.right(p):
            return self._subtree_first_position(self.right(p))
        else:
            walk = p #
            above = self.parent(walk)
            while above is not None and walk == self.right(above):
                walk = above
                above = self.parent(walk)
            return above

    def delete(self, p):
        """Remove the item at given Position"""
        self._validate(p)
        if self.left(p) and self.right(p): # p has two children
            replacement = self._subtree_last_position(self.left(p))
            self._replace(p, replacement.element())
            p = replacement
        parent = self.parent(p)
        self.delete(p)

    def __getitem__(self, k):
        if self.is_empty():
            raise KeyError("Key error: " + repr(k))
        else:
            p = self._subtree_search(self.root(), k)
            if k != p.key():
                raise KeyError("Key error: " + repr(k))
            return p.value()

    def __setitem__(self, key, value):
        if self.is_empty():
            leaf = self._add_root(self._Item(key, value))
        else:
            p = self._subtree_search(self.root(), key)
            if p.key() == key:
                p.element()._value = value
                return
            else:
                item = self._Item(key, value)
                if p.key() < key:
                    leaf = self._add_right(p, item)
                else:
                    leaf = self._add_left(p, item)

    def __delitem__(self, key):
        if not self.is_empty():
            p = self._subtree_search(self.root(), key)
            if key == p.key():
                self.delete(p)
                return
        raise KeyError("Key Error: "+repr(key))

    def __str__(self):
        nodes = list(self.breadth_first())
        layer_num = int(math.log(len(nodes), 2)) + 1
        nodes_array = []
        for i in range(layer_num):
            nodes_array.append([None]*2**i)

        for i in range(layer_num):
            for j in range(0, 2**i):
                nodes_array[i][j] = nodes[2**i -1 + j].key()

        expr_nodes = ''
        for n in nodes_array:
            expr_nodes += str(n) + '\n'

        return str(expr_nodes)




